#include <malloc.h>
#include <stdio.h>
#include "tree.h"
#include "buildsettings.h"
int RemoveSubtree(TreeNode *parent, TreeNode *child);
int tree_InsertChild(TreeNode *parent, TreeNode *child);
int tree_RemoveSubtree(TreeNode *parent, TreeNode *child);
int tree_Print(Tree t);
void treenode_Print(TreeNode *tn, int indent);

/*!
  Create an empty tree structure.
  /return The new tree
*/
Tree new_Tree()
{
	Tree t;
	t.Root = 0x0;
	t.RemoveSubtree = tree_RemoveSubtree;
	t.InsertChild = tree_InsertChild;
	t.FreeTreeNode = destroy_TreeNode;
	t.Print = tree_Print;
	return t;
}


/*!
  Create an empty tree node.
  /return A pointer to a tree node allocated with malloc.
*/
TreeNode *new_TreeNode()
{
	TreeNode *tn = (TreeNode*)malloc(sizeof(TreeNode));
	tn->Parent = 0x0;
	tn->NextSibling = 0x0;
	tn->PreviousSibling = 0x0;
	tn->FirstChild = 0x0;
	tn->LastChild = 0x0;
	tn->Value = 0x0;
	tn->ValueType = TREENODEVALUETYPE_EMPTY;

	tn->Print = treenode_Print;
	return tn;
}

/*!
  Recursively destroy node n and all its children.
  also destroys all data in the Value field
  /param n A pointer to a tree node allocated with malloc.
  /return A global error code
*/
int destroy_TreeNode(TreeNode *n)
{
	int result=0;
	TreeNode *rc;
	TreeNode *rcNext;
	TreeNode *p;

	if (n==0x0)
		return result;

	result=result+1;
	rc = n->FirstChild;
	// For every node in n's child list...
	while (rc != 0x0)
	{
		// Recursively free the child
		rcNext = rc->NextSibling;
		result=result+destroy_TreeNode(rc);
		rc = rcNext;
	}
	p = n->Parent;
	// If n is not the root, remove n from p's child list
	if (p != 0x0)
		tree_RemoveSubtree(p, n);
	// Free associated value field if necessary
	if (n->Value != 0x0)
		free(n->Value);
	printf("Freeing node 0x%lX\n", (ADDRESS)n);
	free(n);
	
	return result;
}

/*!
  Add a leaf to the tree.
  /param parent The parent tree node
  /param child The child tree node to add
  /return A global error code
*/
int tree_InsertChild(TreeNode *parent, TreeNode *child)
{
	if (parent==0x0 || child==0x0)
		return EC_INVALID_ARGUMENT;
	// Check for empty list condition
	if (parent->FirstChild == 0x0)
	{
		parent->FirstChild = child;
		parent->LastChild = child;
	}
	// Generic case
	else
	{
		child->PreviousSibling = parent->LastChild;
		parent->LastChild->NextSibling = child;
		parent->LastChild = child;
	}
	return EC_SUCCESS;
}
/*!
  Remove a subtree from a parent's child list.
  Removes the parent's reference to the subtree root. This function doesn't free the memory that the subtree uses but the subtree will be entirely removed. The user should get a pointer to the parent and subtree before calling this function.
  /param parent The parent of the child to remove
  /param child The child to remove
  /return A global error code
*/
int tree_RemoveSubtree(TreeNode *parent, TreeNode *child)
{
	TreeNode *rc = parent->FirstChild;
	TreeNode *rcPrev =0x0;
	int removed=0;

	if (parent == 0x0 || child == 0x0)
		return EC_INVALID_ARGUMENT;
	// Search for child in parent's child list
	while (rc != 0x0)
	{
		// If found, remove it from the list
		if (rc == child) {
			if (rcPrev != 0x0)
				rcPrev->NextSibling = rc->NextSibling;
			if (rc->NextSibling != 0x0)
				rc->NextSibling->PreviousSibling = rcPrev;
			removed = 1;
		}
	}
	if (removed == 1)
		return EC_SUCCESS;
	else
		return EC_NOT_FOUND;
}

/*!
  Formatted printing for a subtree.
  Does a preorder walk of the tree and prints memory locations of nodes and values with indentation. This is a helper function. Use PrintTree(Tree t)
  /param n The root of the tree
  /param indent A parameter for tracking the depth of the search
*/
void treenode_Print(TreeNode *n, int indent)
{
	int i;
	TreeNode *rc;

	if (n == 0x0)
		return;

	// Print current node
	for (i=0; i<indent; i++)
	{
		printf(" ");
	}
	printf("0x%lX: 0x%lX (%d)\n", (ADDRESS)n, (ADDRESS)n->Value, n->ValueType);

	// Recursively print every child
	rc = n->FirstChild;
	while (rc != 0x0)
	{
		treenode_Print(rc, indent+2);
		rc = rc->NextSibling;
	}
}
/*!
  Formatted printing for a tree.
  Prints to stdout
  /param t The tree to print
  /return A global error code
*/
int tree_Print(Tree t)
{
	if (t.Root == 0x0)
		return EC_INVALID_ARGUMENT;
	treenode_Print(t.Root, 0);
	return EC_SUCCESS;
}

